package oct2013;

public class MedianofTwoSortedArrays {
	public double findMedianSortedArrays(int A[], int B[]) {
		int n = A.length, m = B.length;
		return 0.5 * (findKth(A, 0, n - 1, B, 0, m - 1, (m + n + 1) / 2) + findKth(
				A, 0, n - 1, B, 0, m - 1, (m + n + 2) / 2));
	}

	int findKth(int[] A, int la, int ra, int[] B, int lb, int rb, int k) {
		if (la > ra)
			return B[lb + k - 1];
		if (lb > rb)
			return A[la + k - 1];
		if (k == 1)
			return Math.min(A[la], B[lb]);
		if (ra - la > rb - lb) {
			return findKth(B, lb, rb, A, la, ra, k);
		}
		int ma = Math.min(ra + la >> 1, la + k / 2 - 1);
		int mb = k - (ma - la + 1) + lb - 1;
		if (A[ma] < B[mb]) {
			return findKth(A, ma + 1, ra, B, lb, rb, k - (ma - la + 1));
		} else {
			return findKth(A, la, ra, B, mb + 1, rb, k - (mb - lb + 1));
		}
	}

	public static void main(String[] args) {
		MedianofTwoSortedArrays a = new MedianofTwoSortedArrays();
		a.findMedianSortedArrays(new int[] { 2, 3, 4 }, new int[] { 1 });
	}
}
